#include <gtest/gtest.h>
#include "common.h"
#include <stack>

using namespace ::std;

template <typename T = int>
void printVec(vector<T>& out) {
    // cbegin() 返回 const_iterator，访问时不可以改变元素的值 Container<T>::const_iterator
    // for (auto it = out.cbegin(); it != out.cend() ; ++it) cout << *it << " "; cout << endl;
    for_each(out.begin(), out.end(), [=](T x) { cout << x << " "; });
    cout << endl;
}

void printBinary(TreeNode* root) {
	vector<int> out = makeBinaryTreeToVector(root);
	printVec(out);
}

// 栈
// 思考哪些元素需要入栈，每个元素出栈的时候要进行哪些操作
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
		if(nullptr == root) return {};
		vector<int> vec;
		stack<TreeNode*> stac;
		TreeNode* cursor = root;
		while(cursor != nullptr) {
			if(cursor != nullptr) {
				while(cursor->left != nullptr) {
					stac.push(cursor);
					cursor = cursor->left;
				}
				// printBinary(cursor);
				vec.push_back(cursor->val);
			}

			if(cursor->right != nullptr) {
				cursor = cursor->right;
			} else {
				while(!stac.empty() && nullptr == cursor->right) {
					cursor = stac.top();
					vec.push_back(cursor->val);
					stac.pop();
				}
				if(stac.empty() && nullptr == cursor->right) cursor = nullptr;
				else cursor = cursor->right;
			}
		}
		return vec;
    }
};

class InorderTraversalCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(InorderTraversalCheck, testInorderTraversal_1) {
	vector<int> vec = {};
	TreeNode* root = makeVectorToBinaryTree(vec);
	EXPECT_TRUE(vector<int>({}) == (solution.inorderTraversal(root)));
}

TEST_F(InorderTraversalCheck, testInorderTraversal_2) {
	vector<int> vec = {1};
	TreeNode* root = makeVectorToBinaryTree(vec);
	EXPECT_TRUE(vector<int>({1}) == (solution.inorderTraversal(root)));
}

TEST_F(InorderTraversalCheck, testInorderTraversal_3) {
	vector<int> vec = {1,INT_MAX,2,3};
	TreeNode* root = makeVectorToBinaryTree(vec);
	// vector<int> out = makeBinaryTreeToVector(root);
	// printVec(out);
	// vector<int> result = solution.inorderTraversal(root);
	// printVec(result);
	EXPECT_TRUE(vector<int>({1,3,2}) == (solution.inorderTraversal(root)));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
